package org.example.sword2offer.primary;

/**
 * @author: lynn
 * @Descript:链表重排，NC2
 * @date: 2021/6/16 22:00
 * //题目位置：https://www.nowcoder.com/questionTerminal/3d281dc0b3704347846a110bf561ef6b?toCommentId=427929
 * @version: 1.0
 */
public class Q72_ReOrderListNode {
    public static void main(String[] args) {
        ListNode listNode=new ListNode(1);
        listNode.next=new ListNode(2);
        listNode.next.next=new ListNode(3);
        listNode.next.next.next=new ListNode(4);
        listNode.next.next.next.next=new ListNode(5);
        reorderList(listNode);
        System.out.println("xxx");
    }
    //解法: https://www.bilibili.com/video/BV1Kt4y1Y7Wy?from=search&seid=14171669766595752617
    public static void reorderList(ListNode head) { //fixme 美团2面，重新排序链表  l0->ln->l1->ln-1->..
        if(head == null || head.next == null) return;
        ListNode fast = head;ListNode slow = head;// 快慢指针找到中间节点
        while(fast.next != null && fast.next.next != null){ //fixme 中间是 &&
            fast = fast.next.next;slow = slow.next;
        }
        ListNode after = slow.next;// 拆分链表，并反转中间节点之后的链表
        slow.next = null;ListNode pre = null;
        while(after != null){
            ListNode temp = after.next;
            after.next = pre;
            pre = after;
            after = temp;
        }
        ListNode first = head;after = pre;
        while(first != null && after != null){// 合并两个链表
            ListNode ftemp = first.next; //第一步:保存first的next
            ListNode aftemp = after.next; //第二步：保存last的next
            first.next = after;  //将after插入到first和first.next之间
            after.next = ftemp;  //将after插入到first和first.next之间
            after = aftemp;  //第五步:前进，第一步和第二步要提前保存，因为后面要修改
            first = ftemp;   //第六步:前进
        }
    }
    private static class ListNode{
        int val;
        ListNode next;
        ListNode(int val){
            this.val=val;
            this.next=null;
        }
    }
}
